/*
 * Quercia Luciano
 * Algoritmi e Strutture Dati
 * a.a. 2009-10
 */


#ifndef _ALBEROBIN_H_
#define _ALBEROBIN_H_

#define NDEBUG
#include <cassert>

#include "nodobin.h"

template <class T>
class Alberobin {
public:
	Alberobin();
	Alberobin(int max);
	~Alberobin();


	typedef int posizione;


	//Operatori
	void creaBinAlbero();
	bool binAlberoVuoto();
	posizione binRadice()               throw (char const *) ;
	posizione padre(posizione)          throw (char const *) ;
	posizione figlioSinistro(posizione) throw (char const *);
	posizione figlioDestro(posizione)   throw (char const *);
	bool sinistroVuoto(posizione)       throw (char const *);
	bool destroVuoto(posizione)         throw (char const *);

	void insBinRadice()        			throw (char const *);
	void insBinRadice( T )				throw (char const *);
	void insBinRadice( Alberobin )		throw (char const *);

	void insFiglioSinistro( posizione ) 			throw (char const *);
	void insFiglioSinistro( posizione, T )			throw (char const *);
	void insFiglioSinistro( posizione, Alberobin )	throw (char const *);

	void insFiglioDestro( posizione )				throw (char const *);
	void insFiglioDestro( posizione, T )			throw (char const *);
	void insFiglioDestro( posizione, Alberobin )	throw (char const *);

	void cancSottoBinAlbero( posizione )throw (char const *);


	T leggiNodo(posizione)              throw (char const *);
	void scriviNodo(T,posizione)		throw (char const *);


	//overloading operatori



	//operatori personalizzati
	void print();
	void print(posizione);

	void visitaPreordine();
	void visitaPostordine();
	void visitaSimmetrica();
	void visitaPreordine(posizione);
	void visitaPostordine(posizione);
	void visitaSimmetrica(posizione);

private:
	void copiaAlbero(posizione, Alberobin, posizione) throw (char const *);

	static const int NIL = -1;
	int sizeMax;
	int nNodi;
	posizione inizio;
	posizione libera;

	NodoBin<T> * spazio;
};



/*****************************
 *        DEFINIZIONI        *
 *  dei metodi di Alberobin  *
 *****************************/


template <class T>
Alberobin<T>::Alberobin() {
	sizeMax = 100;

	nNodi = 0;
	inizio = NIL;
	libera = NIL;

	spazio = new NodoBin<T>[ sizeMax ];
	creaBinAlbero();
}

template <class T>
Alberobin<T>::Alberobin( int max ) {
	sizeMax = max;

	nNodi = 0;
	inizio = NIL;
	libera = NIL;

	spazio = new NodoBin<T>[ sizeMax ];
	creaBinAlbero();
}


template <class T>
Alberobin<T>::~Alberobin() {}


template <class T>
void Alberobin<T>::creaBinAlbero() {
	T elementoNullo;
	for (int i = 0; i < sizeMax; i++) {
		spazio[i].setPadre( NIL );
		spazio[i].setFiglioSinistro( (i+1) % sizeMax );
		spazio[i].setFiglioDestro( NIL );
		spazio[i].setValue( elementoNullo );
	}
	libera = 0;
}



template <class T>
bool Alberobin<T>::binAlberoVuoto() {
	return ( nNodi == 0 ) ;
}



template <class T>
typename Alberobin<T>::posizione Alberobin<T>::binRadice()  throw (char const *) {
	if ( ! binAlberoVuoto() )
		return ( inizio ) ;
	else
		throw "L'albero è vuoto." ;
}



template <class T>
typename Alberobin<T>::posizione Alberobin<T>::padre(posizione pos) throw (char const *) {
	if ( !binAlberoVuoto() )
		if ( pos != binRadice() )
			return ( spazio[pos].getPadre() ) ;
		else
			throw "La radice non ha padre";
	else
		throw "L'albero e' vuoto.";
}



template <class T>
typename Alberobin<T>::posizione Alberobin<T>::figlioSinistro(posizione pos) throw (char const *) {
	if ( !binAlberoVuoto() ) {
		posizione left = spazio[pos].getFiglioSinistro();
		if ( left != NIL )
			return ( left ) ;
		else
			throw "Il nodo non ha il figlio sinistro";
	}
	else
		throw "L'albero e' vuoto. Non ci sono nodi.";
}



template <class T>
typename Alberobin<T>::posizione Alberobin<T>::figlioDestro(posizione pos) throw (char const *) {
	if ( !binAlberoVuoto() ) {
		posizione right = spazio[pos].getFiglioDestro();
		if ( right != NIL )
			return ( right ) ;
		else
			throw "Il nodo non ha il figlio destro";
	}
	else
		throw "L'albero e' vuoto. Non ci sono nodi.";
}




template <class T>
bool Alberobin<T>::sinistroVuoto(posizione pos)  throw (char const *) {
	if ( !binAlberoVuoto() )
		return ( spazio[pos].getFiglioSinistro() == NIL ) ;
	else
		throw "L'albero e' vuoto. Non ci sono nodi.";
}




template <class T>
bool Alberobin<T>::destroVuoto(posizione pos) throw (char const *) {
	if ( !binAlberoVuoto() )
		return ( spazio[pos].getFiglioDestro() == NIL ) ;
	else
		throw "L'albero e' vuoto. Non ci sono nodi.";
}



template <class T>
void Alberobin<T>::insBinRadice() throw (char const *) {
	if ( binAlberoVuoto() ) {
		inizio = libera;
		libera = spazio[libera].getFiglioSinistro();
		spazio[inizio].setPadre(NIL);
		spazio[inizio].setFiglioSinistro(NIL);
		spazio[inizio].setFiglioDestro(NIL);
		nNodi++;
	}
	else
		throw "L'albero non e' vuoto. Impossibile inserire la radice.";
}


template <class T>
void Alberobin<T>::insBinRadice(T value) throw (char const *) {
	if ( binAlberoVuoto() ) {
		inizio = libera;
		libera = spazio[libera].getFiglioSinistro();
		spazio[inizio].setValue( value );
		spazio[inizio].setPadre(NIL);
		spazio[inizio].setFiglioSinistro(NIL);
		spazio[inizio].setFiglioDestro(NIL);
		nNodi++;
	}
	else
		throw "L'albero non e' vuoto. Impossibile inserire la radice.";
}


template <class T>
void Alberobin<T>::insBinRadice( Alberobin tree )  throw (char const *) {
	if ( binAlberoVuoto() ) {
		if (this->sizeMax >= tree.sizeMax) {
			for (int i=0; i<tree.sizeMax; i++)
				this->spazio[i] = tree.spazio[i];
			this->inizio = tree.inizio;
			this->libera = tree.libera;
			this->nNodi = tree.nNodi;
		}
	}
	else
		throw "L'albero non e' vuoto. Impossibile inserire la radice.";
}


template <class T>
void Alberobin<T>::insFiglioSinistro(posizione pos) throw (char const *) {
	if ( !binAlberoVuoto() )
		if (pos != NIL)
			if ( sinistroVuoto( pos ) )
				if ( nNodi < sizeMax ) {
					posizione p = libera;
					libera = spazio[libera].getFiglioSinistro();

					spazio[p].setPadre(pos);
					spazio[p].setFiglioSinistro(NIL);
					spazio[p].setFiglioDestro(NIL);
					spazio[pos].setFiglioSinistro(p);
					nNodi++;
				} else
					throw "Lunghezza massima raggiunta.";
			else
				throw "Il figlio sinistro del nodo c'e' gia'";
		else
			throw "Posizione non valida.";
	else
		throw "L'albero e' vuoto. Non ci sono nodi.";
}


template <class T>
void Alberobin<T>::insFiglioSinistro(posizione pos, T value) throw (char const *) {
	insFiglioSinistro(pos);

	//se non vengono sollevate eccezioni
	assert( pos != NIL );
	assert( spazio[pos].getFiglioSinistro() != NIL );

	spazio[spazio[pos].getFiglioSinistro()].setValue( value );
}


template <class T>
void Alberobin<T>::insFiglioSinistro(posizione pos, Alberobin tree)  throw (char const *) {
	insFiglioSinistro(pos);
	copiaAlbero( spazio[pos].getFiglioSinistro(), tree, tree.binRadice() );
}


template <class T>
void Alberobin<T>::insFiglioDestro(posizione pos) throw (char const *) {
	if ( !binAlberoVuoto() )
		if (pos != NIL)
			if ( destroVuoto( pos ) )
				if ( nNodi < sizeMax ) {
					posizione p = libera;
					libera = spazio[libera].getFiglioSinistro();
					spazio[p].setPadre(pos);
					spazio[p].setFiglioSinistro(NIL);
					spazio[p].setFiglioDestro(NIL);
					spazio[pos].setFiglioDestro(p);
					nNodi++;
				} else
					throw "Lunghezza massima raggiunta.";
			else
				throw "Il figlio destro del nodo c'e' gia'";
		else
			throw "Posizione non valida.";
	else
		throw "L'albero e' vuoto. Non ci sono nodi.";
}





template <class T>
void Alberobin<T>::insFiglioDestro(posizione pos, T value)  throw (char const *) {
	insFiglioDestro(pos);

	//se non vengono sollevate eccezioni
	assert( pos != NIL );
	assert( spazio[pos].getFiglioDestro() != NIL );

	spazio[spazio[pos].getFiglioDestro()].setValue( value );
}

template <class T>
void Alberobin<T>::insFiglioDestro(posizione pos, Alberobin tree)  throw (char const *) {
	insFiglioDestro(pos);
	copiaAlbero( spazio[pos].getFiglioDestro(), tree, tree.binRadice() );
}


template <class T>
void Alberobin<T>::cancSottoBinAlbero(posizione pos)  throw (char const *) {
	if ( !binAlberoVuoto() ) {

		if ( pos != NIL ) {
			posizione left = spazio[pos].getFiglioSinistro();
			posizione right = spazio[pos].getFiglioDestro();

			if ( left != NIL )
				cancSottoBinAlbero( left );

			if ( right != NIL )
				cancSottoBinAlbero( right );

			if ( pos == binRadice() ) {
				inizio = NIL;
				assert( nNodi == 1 );

			} else {
				posizione daddy = spazio[pos].getPadre();

				if ( spazio[daddy].getFiglioSinistro() == pos )
					spazio[daddy].setFiglioSinistro(NIL);
				else
					spazio[daddy].setFiglioDestro(NIL);

			}

			nNodi--;
			spazio[pos].setFiglioSinistro( libera );
			spazio[pos].setFiglioDestro(NIL);
			spazio[pos].setPadre(NIL);
			libera = pos;
		} else {}
	} else
		throw "L'albero e' vuoto. Non ci sono nodi.";
}



template <class T>
T Alberobin<T>::leggiNodo(posizione pos)  throw (char const *) {
	if ( pos != NIL )
		return ( spazio[pos].getValue() ) ;
}



template <class T>
void Alberobin<T>::scriviNodo(T label, posizione pos) throw (char const *) {
	if ( pos != NIL )
		spazio[pos].setValue(label) ;
}



template <class T>
void Alberobin<T>::print() {
	print( binRadice() );
}

template <class T>
void Alberobin<T>::print(posizione pos) {

	cout << "(" ;

	if ( pos != NIL ) {
		cout << spazio[pos].getValue() ;

		if ( ( spazio[pos].getFiglioSinistro() != NIL)
				|| (spazio[pos].getFiglioDestro() != NIL) ) {

			print( spazio[pos].getFiglioSinistro() );
			print( spazio[pos].getFiglioDestro() );
		}

	} else {}

	cout << ")" ;
}



template <class T>
void Alberobin<T>::visitaPreordine() {
	visitaPreordine( binRadice() );
}



template <class T>
void Alberobin<T>::visitaPostordine() {
	visitaPostordine( binRadice() );
}


template <class T>
void Alberobin<T>::visitaSimmetrica() {
	visitaSimmetrica( binRadice() );
}



template <class T>
void Alberobin<T>::visitaPreordine(posizione pos) {

	if ( !binAlberoVuoto() ) {
		if ( pos != NIL ) {
			cout << spazio[pos].getValue() << " " ;
			visitaPreordine( spazio[pos].getFiglioSinistro() );
			visitaPreordine( spazio[pos].getFiglioDestro() );
		}
	}
}


template <class T>
void Alberobin<T>::visitaPostordine(posizione pos) {

	if ( !binAlberoVuoto() ) {
		if ( pos != NIL ) {
			visitaPostordine( spazio[pos].getFiglioSinistro() );
			visitaPostordine( spazio[pos].getFiglioDestro() );
			cout << spazio[pos].getValue() << " " ;
		}
	}
}


template <class T>
void Alberobin<T>::visitaSimmetrica(posizione pos) {

	if ( !binAlberoVuoto() ) {
		if ( pos != NIL ) {
			visitaSimmetrica( spazio[pos].getFiglioSinistro() );
			cout << spazio[pos].getValue() << " " ;
			visitaSimmetrica( spazio[pos].getFiglioDestro() );
		}
	}
}



template <class T>
void Alberobin<T>::copiaAlbero(posizione pos, Alberobin tree, posizione p) throw (char const *) {
	assert(pos!=NIL);
	if (p!=NIL) {
		spazio[pos].setValue( tree.spazio[p].getValue() );
		if ( tree.spazio[p].getFiglioSinistro() != NIL ) {
			insFiglioSinistro( pos );
			copiaAlbero( spazio[pos].getFiglioSinistro(), tree, tree.spazio[p].getFiglioSinistro() );
		}

		if ( tree.spazio[p].getFiglioDestro() != NIL ) {
			insFiglioDestro( pos );
			copiaAlbero( spazio[pos].getFiglioDestro(), tree, tree.spazio[p].getFiglioDestro() );
		}
	} else {}
}


#endif // _ALBEROBIN_H_
